#include <iostream>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;

int m, n;
int map[2000][2000];
int ans = -1;
int vis[2000][2000] = {0};

struct Node
{
    int x = 1, y = 1;
    int dis = 0;
    int magic = 0;
    int color;
};

struct mycompare
{
    bool operator()(Node a, Node b)
    {
        return a.dis > b.dis;
    }
};



void dij()
{
    priority_queue<Node, vector<Node>, mycompare> q;

    Node root;
    root.color = map[1][1];
    q.push(root);
    vis[root.x][root.y] = 1;

    while(!q.empty())
    {
        Node now = q.top();
        q.pop();
        if(now.x == m && now.y == m)
        {
            ans = now.dis;
            break;
        }

        int x, y;
        x = now.x + 1, y = now.y;
        if(x > 0 && x <= m && y > 0 && y <= m && !vis[x][y]
            && !(now.magic && map[x][y] == -1))
        {
            Node temp;
            temp.x = x;
            temp.y = y;
            if(map[x][y] == -1)
            {temp.dis = now.dis + 2;temp.magic = 1;temp.color = now.color;}
            else if(map[x][y] == now.color)
            {temp.dis = now.dis; temp.color = now.color;}
            else
            {temp.dis = now.dis + 1; temp.color = map[x][y];}
            q.push(temp);
            vis[x][y] = 1;
        }

        x = now.x - 1, y = now.y;
        if(x > 0 && x <= m && y > 0 && y <= m && !vis[x][y]
            && !(now.magic && map[x][y] == -1))
        {
            Node temp;
            temp.x = x;
            temp.y = y;
            if(map[x][y] == -1)
            {temp.dis = now.dis + 2;temp.magic = 1;temp.color = now.color;}
            else if(map[x][y] == now.color)
            {temp.dis = now.dis; temp.color = now.color;}
            else
            {temp.dis = now.dis + 1; temp.color = map[x][y];}
            q.push(temp);
            vis[x][y] = 1;
        }

        x = now.x, y = now.y + 1;
        if(x > 0 && x <= m && y > 0 && y <= m && !vis[x][y]
            && !(now.magic && map[x][y] == -1))
        {
            Node temp;
            temp.x = x;
            temp.y = y;
            if(map[x][y] == -1)
            {temp.dis = now.dis + 2;temp.magic = 1;temp.color = now.color;}
            else if(map[x][y] == now.color)
            {temp.dis = now.dis; temp.color = now.color;}
            else
            {temp.dis = now.dis + 1; temp.color = map[x][y];}
            q.push(temp);
            vis[x][y] = 1;
        }

        x = now.x, y = now.y - 1;
        if(x > 0 && x <= m && y > 0 && y <= m && !vis[x][y]
            && !(now.magic && map[x][y] == -1))
        {
            Node temp;
            temp.x = x;
            temp.y = y;
            if(map[x][y] == -1)
            {temp.dis = now.dis + 2;temp.magic = 1;temp.color = now.color;}
            else if(map[x][y] == now.color)
            {temp.dis = now.dis; temp.color = now.color;}
            else
            {temp.dis = now.dis + 1; temp.color = map[x][y];}
            q.push(temp);
            vis[x][y] = 1;
        }
    }
}

int main()
{
    cin >> m >> n;

    memset(map, -1, sizeof(map));

    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        cin >> map[x][y];
    }

    dij();

    cout << ans;
}